Many matrices appearing in numerical methods for partial differentialequations and integral equations are rank-structured, i.e., they containsubmatrices that can be approximated by matrices of low rank. A relativelygeneral class of rank-structured matrices are $\mathcal{H}^2$-matrices: theycan reach the optimal order of complexity, but are still general enough for alarge number of practical applications. We consider algorithms for performingalgebraic operations with $\mathcal{H}^2$-matrices, i.e., for approximating thematrix product, inverse or factorizations in almost linear complexity. The newapproach is based on local low-rank updates that can be performed in linearcomplexity. These updates can be combined with a recursive procedure toapproximate the product of two $\mathcal{H}^2$-matrices, and these products canbe used to approximate the matrix inverse and the LR or Cholesky factorization.Numerical experiments indicate that the new method leads to preconditionersthat require $\mathcal{O}(n)$ units of storage, can be evaluated in$\mathcal{O}(n)$ operations, and take $\mathcal{O}(n \log n)$ operations to setup.
展开▼
